def isspecial(c):
    """Returns True if given character (c) is special (backslash, star, etc.)."""

    # Special CharacterS
    scs = ['*', '|', '{', '}', '\\', '?', '-']

    if c in scs:
        return True
    return False

def isoptional(c):
    """Returns True if given character (c) indicates optionality (backslash, star, etc.)."""

    ocs = ['*', '?', '{', '}']

    if c in ocs:
        return True
    return False

def split(cs, c):
    """Splits cs at c. Returns table with fragments of cs."""

    fas = []

    # search for c
    for x in xrange(len(cs)):
        if cs[x] == c:

            # split at x
            fa1 = []
            fa2 = []

            y = 0

            while y < x:
                fa1.append(cs[y])
                y = y+1

            # skip cs[x] (c)
            y = y+1

            while y < len(cs):
                fa2.append(cs[y])
                y = y+1

            # list to string conversion
            fa1 = ''.join(fa1)
            fa2 = ''.join(fa2)

            fas.append(fa1)

            for f in split(fa2, c):
                fas.append(f)

            return fas

    # reached end of cs, did not find c
    return [cs]


def pparse(cs, v=False):
    """Deal with brackets."""

    if v:
        print ('... preparsing ' + cs)

    pparsed = []

    i = 0
    while i < len(cs):

        if (cs[i] == '*' or cs[i] == '?') and cs[i+1] == '(':

            j = i+2
            b = []
            k = len(cs)-1

            # find index of matching bracket
            while cs[k] != ')':
                k -= 1

                # reached end of cs, found no matching bracket ??
                if k == j:
                    print 'Missing matching bracket'
                    break

            while j < k:

                b.append(cs[j])
                j = j+1

            if '(' in b:
                bs = pparse(''.join(b), v)
            else:
                if cs[i] == '*':
                    bs = ''.join(b[:-1]) + '-' + str(len(b)) + b[-1] + b[-1] + cs[k+1:]
                elif cs[i] == '?':
                    bs = ''.join(b) + cs[j+1:] + cs[:i] + cs[k+1:]
                # ???
                else:
                    print 'False special character ???'

            if len(cs[:i]) > 0:
                bs += '|' + cs[:i]
            pparsed.append(bs)

            # skip as many characters as were dealt with (in brackets + brackets
            # + special character before brackets)
            i = i + len(b)+3

        else:
            pparsed.append(cs[i])
            i = i+1


    if v:
        print ('... end preparser ' + ''.join(pparsed))

    # list to string
    return ''.join(pparsed)


def blockify(cs, v=False):
    """Parses string (cs) into meaningful parts, or blocks, for the compiler. Separates basic characters from special characters. Returns character table (blocks)."""

    if v:
        print('... blocking ' + cs)

    blocks = []

    # index of current character
    i = 0

    while i < len(cs):

        # normal character
        if not isspecial(cs[i]):
            if v:
                print ('appending ' + cs[i])
            blocks.append(cs[i])

        # case-by-case
        else:

            # false special, skip backslash and add following character as
            # normal character
            if cs[i] == '\\':
                if v:
                    print (cs[i] + ' is backslash, appending ' + cs[i+1])
                i = i+1
                blocks.append(cs[i])

            # star and optional character are blockified in a similar manner
            elif cs[i] == '*' or cs[i] == '?':
                if v:
                    print ('appending ' + cs[i] + cs[i+1])
                blocks.append(cs[i] + cs[i+1])
                i = i+1

            # accept only at least cs[i+1] number of cs[i+2]
            elif cs[i] == '{':

                if v:
                    print ('appending ' + cs[i] + cs[i+1] + cs[i+2] + ' (at least):')

                # add "at least" number of char as regular block
                for z in xrange(int(cs[i+1])):
                    if v:
                        print ('appending ' + cs[i+2])
                    blocks.append(cs[i+2])

                # add star + char
                if v:
                    print ('appending *' + cs[i+2])
                blocks.append('*' + cs[i+2])

                i = i+2

            # accept only at most cs[i+1] number of cs[i+2]
            elif cs[i] == '}':

                if v:
                    print ('appending ' + cs[i] + cs[i+1] + cs[i+2] + ' (at most):')

                # add '?' + char cs[i+1] times
                for z in xrange(int(cs[i+1])):
                    if v:
                        print ('appending ?' + cs[i+2])
                    blocks.append('?' + cs[i+2])

                i = i+2

            elif cs[i] == '-':
                if v:
                    print ('appending ' + cs[i] + cs[i+1] + cs[i+2] + ' (loop):')

                blocks.append(cs[i] + cs[i+1] + cs[i+2])
                i = i+2

            # unknown special! add as normal character, report brutally
            else:
                print ('unrecognized special character: ' + cs[i])
                blocks.append(cs[i])

        # moving on
        i = i+1

    if v:
        print('... end blocker')

    return blocks


def gettrans(b, next):
    """Takes block (b, see blockify()), index of next available state (next), returns primal transition function and a boolean 'eatsnext' whether it eats next block or not."""

    # normal character -> accept exactly one
    if len(b) == 1:
        return [[b, next], False]

    # non-normal character
    elif len(b) == 2:

        # star -> accept 0 to infinity number of following character
        if b[0] == '*':
            return [[b[1], next-1], True]

        # option -> accept 0 to 1 number of following character
        elif b[0] == '?':
            return [[b[1], next], True]

    elif len(b) == 3:

        if b[0] == '-':
            return [[b[2], next-int(b[1])], True]

    else:
        print('unrecognised block: ' + b)


def comp(cs, v=False):
    """Compiles and returns NFA from given sequence of chars (cs). Calls split and blockify. \"Main function\""""

    if v:
        print ('... compiling ' + cs)

    cs = pparse(cs, v)

    # union search
    fas = split(cs, '|')

    fas2 = []

    for fa in fas:

        # copy original string
        s = fa

        # compile
        fa = automate(blockify(fa, v), v)

        # add original string
        fa.append(s)

        fas2.append(fa)

    if v:
        print ('... end compile')

    return fas2

def automate(bs, v=False):
    """Takes 'meaningful' blocks (bs), constructs a finite automata from them and returns it. (automates)"""

    if v:
        print ('... automating ' + str(bs))

    # initialize finite automata (fa) with a list for lists of transition
    # functions and a reject state (fa[0][0]) and an empty list fa[1] for
    # adding indexes of accepting states
    fa = [[[]], []]

    # index of next state
    i = 2

    # index of current block, index of next state is always bi+2
    bi = 0

    # loop over blocks
    while True:

        if v:
            print('now reading block ' + bs[bi])

        # initialize transition table (state)
        tt = []

        # add at least one transition to transition table
        tf = gettrans(bs[bi], i)
        tt.append(tf[0])

        # tf[1] indicates optionality, bi == len(bs)-1 indicates last block
        if tf[1] and bi != len(bs)-1:

            # copy index pointers, and don't touch originals
            j = i
            ci = bi

            # eat all optional functions
            while tf[1]:

                ci = ci+1
                j = j+1

                # add next function as transition to next state (!!!)
                tf = gettrans(bs[ci], j)

                tt.append(tf[0])

                # if reached end of blocks AND last added block was optional
                if ci == len(bs)-1 and tf[1]:

                    # add first optional state as accepting state
                    fa[1].append(i-1)

                    # stop eating
                    break

        # add transition table as state in fa
        fa[0].append(tt)

        # if reached end of blocks
        if bi == len(bs)-1:

            # add accepting state and end loop

            # "default" accepting state
            fa[0].append([[]])

            # if last block was optional
            if tf[1]:

                # add last added state as accepting state, if not already so
                if i-1 not in fa[1]:
                    fa[1].append(i-1)

            # add "default" accepting state
            fa[1].append(i)

            # end loop
            break

        # else: move on (until end of blocks)
        else:
            bi = bi+1
            i = i+1

    if v:
        print ('... end automaton')

    return fa


def tidy(fa0):
    """Removes useless states from fa[0]. Under construction."""

    # ps for pointers
    ps = range(len(fa0))

    for tt in fa0:
        for tf in tt:
            if tf[1] in ps:
                ps.remove(tf[1])

    # now ps only contains indexes of states not pointed to
    ps.sort()


print pparse('aa*(bg)h', True)
print pparse('aa?(bg?(wqe))h', True)
